package com.xixi.basicAlgroithms.sort;

/**
 * @author vincentML
 * @date 2022-01-21  15:58
 */

public class QuickSort
{

    public static int[] quickSort(int[] a){


        quickSort(a, 0, a.length-1);

        return a;
    }


    /*
     * @Desc:
     * @Author vincentML
     * @Date: 2022/1/21 16:08
     * @param a 原始数组
     * @param q 起始下标
     * @param r pivot下标
 * @return int[]
    */
    public static int[] quickSort(int[] a, int q, int r){
        if(r <= q ) return a;
        int index = partition(a, q, r);

        //分别快排拆开的两个分区。
            quickSort(a, q, index - 1);
            quickSort(a, index+1, r);



        return a;
    }


    public static int partition(int[] a, int q, int r){
        int pivot = a[r]; //设定分隔值
        int i = q; //分隔坐标最开始为数组的最前面
        for(int j = q; j < r; ++j){
            if(a[j] < pivot){ //如果a[j]小于a[r],就把i指向下一个，把j放到i前面。j比i快，如果碰到比pivot大的数，i就会停下
                swap(a,i, j);
                ++i;
            }
        }
        swap(a, i, r); //最后，不要忘了把r和i的值对调
        return i;

    }


    public static void swap(int[]a, int i , int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }


    public static void main(String[] args){
        for(int output: quickSort(new int[]{6,8,7,6,3,5,9,4})){
            System.out.println(output);
        }


    }

}
